A document retrieval system uses a trie tree in order to retrieve a desired document, value, or the like from a key at high speed. The technique has been known as disclosed in, for example, Japanese Laid-open Patent Publication No. 59-47669 and Japanese Laid-open Patent Publication No. 11-7451. FIG. 55 is a diagram illustrating an example of a conventional trie tree. The trie tree constructs a tree structure by assigning one node per one character with respect to nodes excluding a root node. The trie tree illustrated in FIG. 55 indicates that values “1, 3, 4, 5, 3, 2, and 1” are respectively assigned to keys “black, green, blue, grey, black, grey, and greenyellow”.
When a conventional retrieval device performs a retrieval process on a trie tree, the retrieval device takes out characters from an input key one by one and traces the nodes of the same key on the trie tree. For example, when the input key “blue” is designated, the retrieval device traces the nodes of the trie tree in order of b, l, u, and e, and detects “4” assigned to “blue”.
Meanwhile, the trie tree illustrated in FIG. 55 has a problem in that the number of nodes increases and thus an amount of used memory increases when the trie tree has a long key. Moreover, there is a problem in that the number of nodes to be compared during a retrieval process increases and thus a retrieval process completion time increases when a key is long.
Therefore, in order to solve the problems on the trie tree, a trie tree called a Patricia tree is devised. The technique has been known as disclosed in, for example, “Radix tree” [online] [Retrieval on Mar. 17, 2009], Internet <ja.wikipedia.org/wiki/%E5%9F%BME6%95%B0%E6%9C%A8 (To avoid URL, “http://” has been omitted)>. FIG. 56 is a diagram illustrating an example of a Patricia tree. The Patricia tree expresses an edge part, through which a node is transited to another node, by using a character string instead of a character, in order to reduce an amount of used memory. In this case, the Patricia tree illustrated in FIG. 56 indicates that values “1, 3, 4, 5, 3, 2, and 1” are assigned to keys “black, green, blue, grey, black, grey, and greenyellow”.
When the conventional retrieval device performs a retrieval process on a trie tree, the retrieval device sequentially compares an input key with the character strings of edge parts to trace the Patricia tree. For example, when the input key “blue” is designated, the retrieval device traces the edge parts of the Patricia tree in order of bl and ue, and detects “4” assigned to “blue”.
However, although the Patricia tree described above can solve a problem on an amount of used memory as compared to a normal trie tree, there is a problem in that an amount of used memory increases when a key has many characters because a node is created for each predetermined character string.